Đương thời, Barbarossa là vị quân vương được kính nể nhất trong thế giới Ki-tô giáo phương Tây.[34] Ông được thần dân yêu mến đến mức người ta truyền tụng rằng: "Nước Đức và Frederick Barbarossa là một thứ nằm trong những con tim người Đức".[6] Ông trở thành là trung tâm của rất nhiều huyền thoại, trong đó có truyền thuyết về vị vua ngự trong núi, giống như truyền thuyết cổ hơn của nước Anh về vua Arthur và Bendigeidfrân. Truyền thuyết kể rằng ông không chết, mà ngủ trong một hang động tại vùng núi Kyffhäuser tại Thüringen, hay đỉnh Untersberg ở Bayern, Đức, cùng với các hiệp sĩ của mình, và rằng bầy quạ sẽ ngừng bay xung quanh núi một khi ông thức giấc, và đưa nước Đức trở lại thời kỳ hoàng kim như xưa cũ. Theo truyền thuyết này, bộ râu đỏ của ông mọc dài tới cái bàn mà ông ngồi. Đôi mắt của ông lim dim như đang ngủ, nhưng thi thoảng ông lại phẩy tay, sai chú tiểu đồng ra xem bầy quạ đã ngưng bay chưa.[35] Một thuyết tương tự, bối cảnh tại Sicilia, được gán cho cháu nội ông là Frederick II, Hoàng đế Đế quốc La Mã thần thánh.[36]

Một huyền thoại khác kể rằng khi Frederick Barbarossa chuẩn bị đánh chiếm thành Milano năm 1158, vợ ông là hoàng hậu Béatrice bị người Milano bắt giữ, và bị dong qua thành phố trên lưng lừa để biêu riếu. Theo nguồn này, để rửa hận, ông buộc giới chức thành này phải dùng răng để lấy hạt quả sung từ hậu môn một con lừa[37] Một nguồn khác thì cho rằng ông buộc tất cả đàn ông trong thành phố phải ngậm phân lừa. Người ta nói rằng hình phạt này là nguồn gốc của động tác sỉ nhục đặt ngón cái giữa ngón trỏ và ngón giữa, với bàn tay nắm chặt.[38]

Frederick Barbarossa được nhìn nhận là một trong những vị vua vĩ đại nhất trong lịch sử Đức. Vào thế kỷ 19, thế kỷ mà nước Đức được thống nhất, ông được chủ nghĩa dân tộc Đức đề cao như một vị anh hùng dân tộc, một trong những người đầu tiên đã chiến đấu vì lý tưởng dân tộc.[39][40] Truyền thuyết về Barbarossa ngủ trong hang chờ đợi sự hồi sinh của Đức, cùng với câu chuyện về Hermann, đã thúc đẩy sự tôn sùng đối với Wilhelm I, vị hoàng đế đầu tiên của một nước Đức thống nhất, và điều này được thể hiện qua các minh họa trong sách vở thời đó và những bích họa Goslar của Wislicenus. Đặc biệt, để thu thập sự ủng hộ về chính trị, Nhà nước Đế quốc Đức đã cho xây dựng đài kỷ niệm Kyffhäuser trên đỉnh núi Kyffhäuser, với ngụ ý ca ngợi Wilhelm I là hậu thân của Frederick I; lễ cung hiến năm 1896 được tổ chức trong ngày 18 tháng 6 với sự có mặt của Đức hoàng Wilhelm II, chính là ngày đăng quang của ông.[7][41]

Trong thời kỳ Đức Quốc xã, Lãnh tụ Adolf Hitler đã tôn vinh Frederick như một trong những tấm gương sáng của lịch sử đất nước. Trên tinh thần đó,[40] khi quân đội Đức tấn công Liên bang Xô viết năm 1941, chiến dịch này đã dược đặt theo tên hiệu của ông là Chiến dịch Barbarossa[42].